#include "Verifier_Agglomerative.h"

Verifier_Agglomerative::Verifier_Agglomerative(int depth,
                                               Cluster_Metric metric,
                                               Splitter& splitter) {
    LOG_ENTER(FIX, "Verifier_Agglomerative::Verifier_Agglomerative");
    LOG(FIX) << "min_ratio=" << min_ratio;

    max_depth = depth;
    cluster_metric = metric;
    cluster_splitter = splitter;

    LOG_EXIT();
}

vector<Tree_Of_Clusters *>
*Verifier_Two_Stage::verify(vector<Cluster*>& children) {

    // First step: split the two clusters recursively as deep as specified
    vector <Cluster*> leaf_clusters;
    subdivide(children[0], leaf_clusters, max_depth);
    subdivide(children[1], leaf_clusters, max_depth);

    // Now, build a list of Cluster-objects from the leaves
    Object_List leaf_meta_objects;
    for (int i=0; i<leaf_clusters.size(); i++) {
        Cluster_Metric_Object *leaf_meta_object = new Cluster_Metric_Object(leaf_objects[i]);
        leaf_meta_objects.append(leaf_meta_object);
    }

    // Treat the list of Cluster-object as one big meta-object.
    Cluster meta_root(leaf_meta_objects.get_whole_span(), 0);
    Cluster_Metric_Object::metric = cluster_metric;

    // Build a tree of cluster-objects, using agglomeration.
    Builder_Agglomerative builder(cluster_metric);
    builder.build(meta_root);

    // With the tree built, keep the right subtree and the left subtree.
    // They are the new fixed-up clusters.
    // But, since we're reporting clusters of objects, and meta-clusters,
    // we need to convert each meta-cluster into an ordinary cluster.
    Tree_Of_Clusters *L = new Tree_Of_Clusters();
    Tree_Of_Clusters *R = new Tree_Of_Clusters();
    gather_elements(L, builder.tree.root->left,  max_depth);
    gather_elements(R, builder.tree.root->right, max_depth);

    vector<Tree_Of_Clusters *> *subtrees = new vector<Tree_Of_Clusters *>();
    subtrees->push_back(L);
    subtrees->push_back(R);

    // Clean up
    leaf_meta_objects.clear();

    return subtrees;
}

// Descend down the tree of meta-clusters, expanding
// each meta-cluster into an ordinary cluster of objects,
// and adding a matching node to the result tree.
Cluster *Verifier_Agglomerative::
gather_elements(Tree_Of_Clusters *result_tree,
                Cluster *meta_root,
                int depth) {

    if (depth > 0) {
        if (meta_root != NULL) {
            Cluster *L = gather_elements(result_tree, meta_root->left, depth-1);
            Cluster *R = gather_elements(result_tree, meta_root->right, depth-1);
            Cluster *cluster = gather_elements(meta_root);

            if (depth == 1)
                result_tree->set_root(cluster);

            result_tree->set_children(root, L, R);

            return cluster;
        }
    }
    return NULL;
}

Cluster* Verifier_Agglomerative::gather_elements(Cluster *meta_cluster) {
    // Coming in, meta_cluster contains a list of objects.
    // Each of these objects is a meta-object, which contains a cluster itself.
    // We need to gather all the clusters in all the meta-objects into one
    // collective cluster.

    // This will be the collective cluster.
    Cluster *result = NULL;

    if (meta_cluster != NULL) {

        // A span within a list of meta-objects.
        LMO_Span span = meta_cluster->span;
        int i=0;
        for (LMO_Iterator iter = span.start; i < span.n; iter++, i++) {
            Labeled_Metric_Object *p = *iter;
            Cluster_Metric_Object *obj = (Cluster_Metric_Object*)(p->object);
            Cluster *cluster = obj->cluster;

            // We've fished the cluster out this meta-object.
            // Now, put it into the result.
            if (i == 0) {
                result = new Cluster(cluster->span, cluster->color);
            }
            else {
                result->append(cluster);
            }
        }
    }

    return result;
}

void Verifier_Agglomerative::subdivide(Cluster *root,
                                       vector<Cluster *leaves>&,
                                       int depth) {
    if (depth == 0 ||
        root->span.n == 1) {
        // we are down to a singleton cluster,
        // or have reached maximum recursive depth
        leaves.push_back(root);
    }
    else {
        // Root is splittable.
        Cluster *child1, *child2;
        splitter->split(root, child1, child2);

        // Recursively subdivide the children.
        subdivide(child1, depth-1);
        subdivide(child2, depth-1);
    }
}
